package com.yoshino.leetcode.interview150.graph.bfs;

import java.util.*;

class Solution {
    public static void main(String[] args) {
        new Solution().ladderLength("hit", "cog",Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
    }

    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        boolean[] vis = new boolean[n * n + 1];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{1, 0});
        while (!queue.isEmpty()) {
            // 点数   到达该点所需步数
            int[] p = queue.poll();
            // 模拟骰子
            for (int i = 1; i <= 6; i++) {
                // 下一个点数
                int nxt = p[0] + i;
                if (nxt > n * n) {
                    break;
                }
                // 得到下一步位置
                int[] rc = id2rc(nxt, n);
                if (board[rc[0]][rc[1]] > 0) {
                    // 存在蛇或者梯子
                    nxt = board[rc[0]][rc[1]];
                }
                if (nxt == n * n) {
                    return p[1] + 1;
                }
                if (!vis[nxt]) {
                    vis[nxt] = true;
                    // 扩展新状态
                    queue.offer(new int[]{nxt, p[1] + 1});
                }
            }
        }
        return -1;
    }

    private int[] id2rc(int id, int n) {
        int r = (id - 1) / n, c = (id - 1) % n;
        // 为奇数行需要倒转
        if (r % 2 == 1) {
            c = n - 1 - c;
        }
        return new int[]{n - 1 - r, c};
    }

    public int minMutation(String start, String end, String[] bank) {
        if (start.equals(end)) {
            return 0;
        }
        Set<String> visited = new HashSet<>();
        char[] keys = {'A', 'C', 'G', 'T'};
        Set<String> cnt = new HashSet<>(Arrays.asList(bank));
        if (!cnt.contains(end)) {
            return -1;
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        visited.add(start);
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 遍历当前轮次：使用步数一样的
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                for (int j = 0; j < 8; j++) {
                    // 每一个字母可以变 3 次
                    for (int k = 0; k < 4; k++) {
                        if (keys[k] != cur.charAt(j)) {
                            StringBuilder sb = new StringBuilder(cur);
                            sb.setCharAt(j, keys[k]);
                            String net = sb.toString();
                            if (!visited.contains(net) && cnt.contains(net)) {
                                // 记录有效的
                                if (net.equals(end)) {
                                    return step;
                                }
                                queue.offer(net);
                                visited.add(net);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 类比上面
        Set<String> dict = new HashSet<>(wordList);
        Set<String> visited = new HashSet<>();
        if (!dict.contains(endWord)) {
            return 0;
        }
        int step = 1;
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        visited.add(beginWord);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                for (int j = 0; j < cur.length(); j++) {
                    for (int k = 0; k < 26; k++) {
                        if (cur.charAt(j) != 'a' + k) {
                            StringBuilder sb = new StringBuilder(cur);
                            sb.setCharAt(j, (char) ('a' + k));
                            String next = sb.toString();
                            if (!visited.contains(next) && dict.contains(next)) {
                                if (next.equals(endWord)) {
                                    return step + 1;
                                }
                                visited.add(next);
                                queue.offer(next);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return 0;
    }
}